import java.util.*;

public class Test {
    /*
    题目1：和为 k 的子数组
     */
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);// 防止第一个元素为 k 的时候
        int sum = 0, ret = 0;
        for(int x : nums){
            sum += x;
            ret += map.getOrDefault(sum - k, 0);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }

        return ret;
    }

    /*
    题目2：和可被 K 整除的子数组
     */
    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, 1);

        int sum = 0, ret = 0;

        for(int x : nums){
            sum += x;
            int ans = (sum % k + k) % k;
            ret += map.getOrDefault(ans , 0);
            map.put(ans, map.getOrDefault(ans, 0) + 1);
        }
        return ret;
    }

    /*
    题目3：连续数组
     */
    public int findMaxLength(int[] nums) {
        int n = nums.length;

        int sum = 0, len = 0;

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        for(int i = 0; i < n; i++){
            sum += nums[i] == 0 ? -1 : 1;
            if(map.containsKey(sum)){
                len = Math.max(len, i - map.get(sum));
            }else{
                map.put(sum, i);
            }
        }
        return len;
    }

    /*
    题目4：矩阵区域和
     */
    // 利用了 二维前缀和 的解题思路
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length, m = mat[0].length;

        int[][] dp = new int[n + 1][m + 1];
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < m + 1; j++){
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        int[][] ret = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                // 这里是坐标映射的细节！
                int x1 = Math.max(0, i - k) + 1 , y1 = Math.max(0, j - k) + 1;
                int x2 = Math.min(n - 1, i + k) + 1, y2 = Math.min(m - 1, j + k) + 1;
                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
            }
        }
        return ret;
    }

    

}
